1. Field of the Invention
The invention concerns a method of scheduling successive tasks by means of a computer by determining a task execution order and an execution start time for each task, no two tasks ever being executed simultaneously. This scheduling is based on a plurality of constraints that the tasks must satisfy. This process is more particularly concerned with applications in which there is only one type of constraint, namely timing constraints: the execution of a task must begin at a time within at least one predetermined time interval relative to an absolute time reference. There are no constraints applying directly to the order of the tasks. The process naturally concerns also applications in which all constraints can be regarded as equivalent to timing constraints relative to an absolute reference.
The method of the invention is applicable in particular to tasks that must be executed successively because they are executed by single means capable of executing only one task at a time, for example: a machine tool, a data bus, a team of workers. In the field of electronic data processing, the method can be applied to the management of a plurality of predetermined tasks to be executed successively in the same processor or on the same bus. In the field of industrial process control, the method can be applied in particular to the management of a so-called field bus used to transmit information successively in accordance with a predetermined series.
2. Description of the Prior Art
The prior art includes many scheduling methods:
so-called polynomial or critical path methods; PA1 linear programming methods, especially the simplex method on which the PROLOG III language is based; PA1 dynamic programming methods that can be applied only to relatively small problems; and PA1 heuristic methods that use some algorithms employing the above methods but further reduce the number of cases to be verified by simplifying certain constraints; the resulting solution is then less than optimal. PA1 said method comprising the following successive steps in this order:
The prior art methods have two drawbacks: they require a long computation time since they systematically verify a very large number of permutations before giving a solution. The computation time is usually proportional to the factorial of the number of tasks to be scheduled.
To schedule repetitive tasks the prior art methods determine the duration of a macrocycle equal to the lowest common multiple of all the task periods and the duration of a microcycle equal to the highest common denominator of all the task periods, and then look for a permutation of the tasks such that all the constraints are satisfied simultaneously, trying out all possible permutations until one verifying this condition is found, the verification being carried out microcycle by microcycle. If a conflict appears within a microcycle the permutation currently being verified is abandoned and another is tried. The work done in connection with verification of that permutation during previous microcycles becomes of no utility since all the constraints previously satisfied are called into question again.
The prior art methods are therefore somewhat impractical for use in industrial applications.
An object of the invention is to propose a scheduling method that is free of these drawbacks so that a solution to a static scheduling problem is obtained faster, and also to enable dynamic scheduling problems to be handled, i.e. to make it possible to carry out rescheduling as and when the number of tasks to be scheduled and/or the constraints applying to those tasks change. Dynamic scheduling can be beneficial in scheduling machining tasks on a machine tool, for example, if the products to be manufactured are highly diverse; for scheduling aircraft take-offs and landings on a runway; for scheduling tasks on a data bus or processor; etc.